//
// Created by Snow on 2023/4/24.
//
#include"graph0.cpp"
void DispPath(MatGraph g,int A[][MAXV],int path[][MAXV])
{
    int i,j,k,s;
    int apath[MAXV],d;//存放一条最短路径的中间顶点（反向）及其顶点个数
    for(i=0;i<g.n;i++)
        for(j=0;j<g.n;j++)
        {
            if(A[i][j]!=INF&&i!=j)//若顶点i和顶点j之间存在路径
            {
                printf("From %d to %d: ",i,j);
                k=path[i][j];
                d=0;
                apath[d]=j;//路径上添加终点
                while(k!=i)//路径上添加中间点
                {
                    d++;
                    apath[d]=k;
                    k=path[i][k];
                }
                d++;
                apath[d]=i;//路径上添加起点
                printf("%d",apath[d]);//输出起点
                for(s=d-1;s>=0;s--)//输出路径上的中间顶点
                    printf(",%d",apath[s]);
                printf("\tlowcost:%d\n",A[i][j]);
            }
        }
}
void Floyd(MatGraph g)
{
    int A[MAXV][MAXV],path[MAXV][MAXV];
    int i,j,k;
    for(i=0;i<g.n;i++)
    {
       for(j=0;j<g.n;j++)
       {
           A[i][j]=g.edges[i][j];
           if(i!=j&&g.edges[i][j]<INF)//顶点i到j有边时
               path[i][j]=i;
           else//顶点i到j没有边时
               path[i][j]=-1;
       }
    }
    for(k=0;k<g.n;k++)//依次考察所有顶点
    {
        for(i=0;i<g.n;i++)
            for(j=0;j<g.n;j++)
                if(A[i][j]>A[i][k]+A[k][j])
                {
                    A[i][j]=A[i][k]+A[k][j];//修改最短路径长度
                    path[i][j]=path[k][j];//修改最短路径
                }
    }
    DispPath(g,A,path);//输出最短路径
}
int main()
{
    MatGraph g;
    int A[MAXV][MAXV]={
            {0,5,INF,7},
            {INF,0,4,2},
            {3,3,0,2},
            {INF,INF,1,0}};
    int n=4, e=8;
    CreateMat(g,A,n,e);			//建立《教程》中图8.41的邻接矩阵
    printf("g:\n");
    DispMat(g);					//输出邻接矩阵
    Floyd(g);
    return 1;
}